package com.mystudy.leetcode.problem.sort.p_976;

/**
 * @program: infoalgorithm
 * @description: 三角形的最大周长
 * @author: zhouzhilong
 * @create: 2019-07-31 17:27
 **/

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
 * <p>
 * 如果不能形成任何面积不为零的三角形，返回 0。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：[2,1,2]
 * 输出：5
 * 示例 2：
 * <p>
 * 输入：[1,2,1]
 * 输出：0
 * 示例 3：
 * <p>
 * 输入：[3,2,3,4]
 * 输出：10
 * 示例 4：
 * <p>
 * 输入：[3,6,2,3]
 * 输出：8
 *  
 * <p>
 * 提示：
 * <p>
 * 3 <= A.length <= 10000
 * 1 <= A[i] <= 10^6
 */
public class Solution {
    /**
     * logger
     */
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    @Test
    public void test() {
        int[] arr = new int[]{1,2,1};
        int i = largestPerimeter(arr);
        LOGGER.debug("i = [{}]", i);
    }

    /**
     * 解题思路为，从最大的节点开始，尽可能的找到可以组成三角形的最大的两个边
     *
     * @param A
     * @return
     */
    public int largestPerimeter(int[] A) {
        //先计数排序
        int min = A[0];
        int max = A[0];
        for (int i = 0; i < A.length; i++) {
            if (A[i] > max) {
                max = A[i];
            }
        }

        for (int i = 0; i < A.length; i++) {
            if (A[i] < min) {
                min = A[i];
            }
        }

        int[] result = new int[max - min + 1];
        for (int i = 0; i < A.length; i++) {
            result[A[i] - min]++;
        }
        int count = 0;
        for (int i = 0; i < result.length; i++) {
            while (result[i] > 0) {
                A[count] = i + min;
                result[i]--;
                count++;
            }
        }
        LOGGER.debug("result = [{}]",result);
        LOGGER.debug("A = [{}]",A);

        //现在A是排序好的了
        int len = A.length;
        for (int i = len-1; i >= 2; i--) {
            for (int j = i - 1; j >= 1; j--) {
                for (int k = j - 1; k >= 0; k--) {
                    if (isSquare(A[i], A[j], A[k])) {
                        int girth = A[i] + A[j] + A[k];
                        return girth;
                    }
                }
            }
        }
        return 0;
    }


    private boolean isSquare(int x, int y, int z) {
        if(x+y>z){
            return true;
        }
        return false;
    }
}
